import java.util.Date;

public class ListNode<E> {




    public static class Node<E>{
        E date;//元素
        Node next;//指针

        public Node(E date) {
            this.date = date;
        }
    }

    //定义一个头节点
    public Node head;

    //头插法
    public void addFirst(E date) {
        Node<E> node = new Node<>(date);
        node.next = head;
        head = node;
    }

    //尾插法
    public void addLast(E data) {
        Node<E> node = new Node<>(data);
        //判断有没有结点
        if (head == null) {
            head = node;
            return;
        }
        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

    //头删
    public void deleteFirst() {
        //判断是否为空
        if (head == null) {
            return;
        }
        head = head.next;
    }

    //尾删
    public void deletelast() {
        //判断是否为空
        if (head == null || head.next == null) {
            head = null;
            return;
        }
        Node cur = head;
        while (cur.next.next != null) {
            cur = cur.next;
        }
        cur.next = null;
    }

    //指定删除结点
    public void delete(int index) {
        Node prev = head;
        //删除头节点
        if (index == 1) {
            head = head.next;
            return;
        }
        int count = 1;
        while (prev.next != null && count < index - 1) {
            count++;
            prev = prev.next;
        }
        if (prev.next == null || count > index) {
            return;
        }
        Node cur = prev.next;
        prev.next = cur.next;

    }

    //判断下标是否越界
    public void checkPosInAdd(int index) {

        if (index > size() || index < 0) {
            throw new Subscript("下标越界");
        }
    }

    //任意位置插入,第一个数据节点为0号下标
//    public void addIndex(int index,E data) {
//        Node node=new Node(data);
//        //如果index为0则调用头插
//        try {
//            checkPosInAdd(index);
//        }catch (Subscript e){
//            e.printStackTrace();
//            return;
//        }
//        //头插
//        if (index==0) {
//            addFirst(data);
//            return ;
//        }
//        if (index==size()) {
//            addLast(data);
//            return ;
//        }
//     //写一个查找指定位置的前一个结点的方法
//       Node cur= Find(index);
//        node.next=cur.next;
//        cur.next=node;
//        return ;
//    }
    public void addIndex(int index, E date) {
        int count = 1;//结点从1开始，数组从0开始
        Node cur = head;
        //因为要找到前一个位置的结点，所以循环条件是count<index-1
        while (count < index - 1 && cur != null) {
            cur = cur.next;
            count++;
        }
        //当cur为空时说明index超出链表长度,
        //当count>index时，说明index是一个小于1的值是一个非法的位置
        if (cur == null || count > index) {
            return;
        }
        //当判断要插入的位置存在时，则创建这个结点
        Node node = new Node(date);
        node.next = cur.next;
        cur.next = node;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(E key) {
        Node cur = head;
        while (cur != null) {
            if (cur.date.equals(key)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //删除第一次出现关键字为key的节点
    public void remove(E key) {

        if (head == null) {
            return;
        }
        Node cur = head;
        while (cur.next != null) {
            if (cur.next.date.equals(key)) {
                cur.next = cur.next.next;
            }
            cur = cur.next;
        }
        if (head.date.equals(key)) {
            head = head.next;
        }
    }

    //删除所有值为key的节点
    public void removeAllKey(E key) {

    }

    //修改单链表中指定的结点
    public void revise(int index, E val) {
        Node cur = Find(index);
        if (cur == null) {
            return;
        }
        cur.date = val;
    }

    //得到单链表的长度
    public int size() {
        Node cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }


    //打印单链表
    public void display() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.date + "->");
            cur = cur.next;
        }
        System.out.println("null");
    }

    //删除单链表
    public void clear() {
        head = null;
    }

    //查找并返回任意下标的结点
    public Node Find(int index) {
        //判断下标
        Node cur = head;
        while (index > 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    //    //查找并返回任意下标的前一个结点
//    public Node Find(int index) {
//        //判断下标
//        Node cur=head;
//        while (index-1>0) {
//            cur=cur.next;
//            index--;
//        }
//        return cur;
//    }
    public Node<E> reverseList2(Node<E> head) {
        //翻转单链表
        if (head == null) {
            return null;
        }
        //判断是不是只有一个结点
        if (head.next == null) {
            return head;
        }
        //创建两个指针
        Node prev = head.next;
        Node cur = prev.next;
        head.next = null;
        while (true) {
            prev.next = head;
            head = prev;
            prev = cur;
            if (prev == null) {
                return head;
            }
            cur = cur.next;
        }
    }

    public Node<E> reverseList1(Node<E> head) {
        //翻转单链表
        //判断如果为kong
        if (head == null) {
            return null;
        }
        //判断如果只有一个结点
        if (head.next == null) {
            return head;
        }
        //利用头插法
        Node prev = null;
        while (prev != null) {
            Node cur = head.next;
            head.next = prev;
            prev = head;
            head = cur;
        }
        head = prev;
        return head;
    }

    public Node<E> removeElements(Node<E> head, int val) {
        //删除所有指定元素
        if (head == null) {
            return null;
        }
        Node prev = head;
        Node cur = head.next;
        while (cur != null) {
            if (cur.date.equals(val)) {
                prev.next = cur.next;
            } else {
                prev = cur;
            }
            cur = cur.next;
        }

        if ((int) head.date == val) {
            head = head.next;
        }
        return head;
    }

    public Node<E> middleNode(Node<E> head) {
        //查找中间结点
        if (head.next == null) {
            return head;
        }
        Node prve = head;
        Node cur = head;
        while (cur != null && cur.next != null) {
            prve = prve.next;
            cur = cur.next.next;
        }
        return prve;
    }

    public Node<E> FindKthToTail(Node<E> head, int k) {
        if (k <= 0 || head == null) {
            return null;
        }
        int j = 0;
        Node prev = head;
        Node cur = head;
        while (j < k && cur != null) {
            cur = cur.next;
            if (cur == null) {
                return null;
            }
            j++;
        }
        while (cur != null) {
            prev = prev.next;
            cur = cur.next;
        }
        return cur;

    }

    public Node<E> mergeTwoLists(Node<E> list1, Node<E> list2) {

        //定义一个哨兵位
        Node<Integer> newhead = new Node<>(0);
        while (list1 != null && list2 != null) {
            if ((int) list1.date <= (int) list2.date) {
                newhead.next = list1;
            } else {
                newhead.next = list2;
            }
        }
        if (list1 != null) {
            newhead.next = list1;
        } else newhead.next = list2;
        return newhead.next;
    }

    public boolean chkPalindrome(Node A) {
        // write code here
        //链表的回文结构,利用头插法
        if (A == null) {
            return false;
        }
        if (A.next == null) {
            return true;
        }
        Node prev = A;
        Node cur = A;
        while (cur != null && cur.next != null) {
            prev = prev.next;
            cur = cur.next.next;
        }
        Node p1 = prev;
        Node p2 = prev.next;
        while (p2 != null) {
            Node p3 = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = p3;
        }
        prev = A;
        while (p1 != prev) {
            if (p1.date != prev.date) {
                return false;
            }
            if (prev.next == p1) {
                return true;
            }
            p1 = p1.next;
            prev = prev.next;
        }
        return true;
    }

    public Node reverseList3(Node head) {

        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        Node prev = head;
        Node cur = head.next;
        while (cur != null) {
            Node curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;

    }

    public Node getIntersectionNode(Node headA, Node headB) {
        //一个链表为空永远不可能香蕉
        if (headA == null && headB == null) {
            return null;
        }
        Node prve = headA;
        Node cur = headB;
        int count = 0;
        int sum = 0;
        while (cur != null && prve != null) {
            cur = cur.next;
            prve = prve.next;
            count++;
            sum++;
        }
        Node p1 = cur != null ? cur : prve;
        boolean p = cur != null ? true : false;
        while (p1 != null) {
            p1 = p1.next;
            count++;
        }
        prve = headA;
        cur = headB;
        int n = count - sum;
        if (p) {
            while (n > 0) {
                cur = cur.next;
                n--;
            }
        } else {
            while (n > 0) {
                prve = prve.next;
                n--;
            }
        }
        while (cur != prve) {
            cur = cur.next;
            prve = prve.next;
        }
        return cur;
    }

    public Node sortList(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node newhead=new Node(0);
        newhead.next=head;
        Node prev=head;
        Node cur=head.next;
        //定义一个最后结点的指针
        Node lasthead=prev;
        //定义prev的前一个结点的地址
        Node newprev=newhead;
        while (cur!=null) {
            Node curNext=cur.next;
            if (prev.date>=cur.date) {
                newprev.next=cur;
                cur.next=prev;
                lasthead.next=curNext;
                prev=newhead.next;
                newprev=newhead;
            }else {
                //不大于的时候
                newprev=prev;
                prev=prev.next;
            }
            cur=curNext;
        }

        return newhead.next;
    }
}
class Subscript extends RuntimeException {
    public Subscript() {
    }

    public Subscript(String message) {
        super(message);
    }
}